package com.company.dp;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/ransom-note/
 * 给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，
 * 判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。
 * 如果可以构成，返回 true ；否则返回 false。
 *
 * (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)
 * @date 2019/11/14 15:11
 */

public class CanConstruct {

    public static void main(String[] args) {
        System.out.println(canConstruct("aa","ab"));
    }

    public static boolean canConstruct(String ransomNote, String magazine) {

        char[] ransomNoteChars = ransomNote.toCharArray();
        char[] magazineChars = magazine.toCharArray();
        Arrays.sort(ransomNoteChars);
        Arrays.sort(magazineChars);
        int i = 0;
        int j = 0;
        for (i = 0; i < ransomNoteChars.length; i++) {
            char c = ransomNoteChars[i];
            boolean flag =false;
            for (; j < magazineChars.length; j++) {
                if (magazineChars[j] == c) {
                    j++;
                    flag = true;
                    break;
                }
            }
            if (!flag) return false;
        }


        return true;
    }
}
